#define _CRT_SECURE_NO_WARNINGS
#include"sort.h"
void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int exchange = 0;
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				Swap(&a[j], &a[j + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0) {
			break;
		}
	}
}

void InsertSort(int* a, int n) {
	for (int i = 1; i < n; i++) {
		int tmp = a[i];
		int end = i - 1;
		while (end >= 0) {
			if (a[end] > tmp) {
				a[end + 1] = a[end];
			}
			else {
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}

void SelectSort(int* a, int n) {
	int left = 0;
	int right = n - 1;
	while (left < right) {
		int maxi = left;
		int mini = left;
		for (int i = left; i <= right; i++) {
			if (a[i] > a[maxi]) {
				maxi = i;
			}
			if (a[i] < a[mini]) {
				mini = i;
			}
		}
		Swap(&a[left], &a[mini]);
		if (maxi == left) {
			maxi = mini;
		}
		Swap(&a[maxi], &a[right]);
		left++;
		right--;
	}
}
int Getmidi(int* a, int left, int right) {
	int l = a[left];
	int r = a[right];
	int mid = a[(left + right) / 2];
	if (l < r) {
		if (mid > r) {
			return right;
		}
		else {
			if (mid > l) {
				return (left + right) / 2;
			}
			else {
				return left;
			}
		}
	}
	else if (l > r) {
		if (mid > l) {
			return left;
		}
		else {
			if (mid > r) {
				return (left + right) / 2;
			}
			else {
				return right;
			}
		}
	}
	else {
		return left;
	}
}
void QuickSort(int* a, int left, int right) {
	if (left >= right) {
		return;
	}
	int midi = Getmidi(a, left, right);
	Swap(&a[midi], &a[left]);
	int key = a[left];
	int l = left;
	int r = right;
	while (l < r) {
		while (l < r && a[r] >= key) {
			r--;
		}
		while (l < r && a[l] <= key) {
			l++;
		}
		Swap(&a[l], &a[r]);
	}
	Swap(&a[l], &a[left]);
	QuickSort(a, left, l - 1);
	QuickSort(a, l + 1, right);
}

void QuickSort3(int* a, int left, int right) {
	if (left >= right) {
		return;
	}
	int key = a[left];
	int l = left ;
	int r = left + 1;
	while (r <= right) {
		if (a[r] < key && ++l != r) {
			Swap(&a[l], &a[r]);
		}
		r++;
	}
	Swap(&a[left], &a[l]);
	QuickSort3(a, left, l - 1);
	QuickSort3(a, l + 1,right);

}